\documentclass{ctexart}
\usepackage{diagbox}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{framed}
\usepackage{color}
\usepackage{subfigure}
\usepackage{array,tabularx}
\definecolor{shadecolor}{rgb}{0.92,0.92,0.92}
\geometry{a4paper,scale=0.8}
\title{AVL树区间范围内元素输出的函数实现}


\author{梁婧 \\ 信息与计算科学，3210105193}

\begin{document}

\maketitle

\section{PrintRange 函数设计思路}
处理树中的结点使用递归的方法。当结点的 Key(X) 大于最小值时，转去检查结点的左儿子。再判断结点的 Key(X) 是否符合输出条件，决定是否输出。然后判断结点的 Key(X) 是否小于最大值，若成立，则转去检查结点的右儿子。


\section{PrintPange 函数实现}

\subsection{private函数}
\begin{shaded}
\begin{verbatim}
    void PrintRange( const Comparable & k1, const Comparable & k2, 
                     AvlNode *t )
    {
1      if( t == nullptr)
2      return;

3      if( t->element > k1)
4      PrintRange( k1, k2, t->left);

5      if( k1 <= t->element && t->element <= k2)
6      cout << t->element << "   ";

7      if( t->element < k2)
8      PrintRange( k1, k2, t->right);

9      return;
    }

\end{verbatim}
\end{shaded}
\section{理论分析}
\subsection{正确性}
分析程序的递归流程可知，程序的运行顺序是先找到了树中关键字大于 K1 的最小结点，这一步去掉了所有关键字小于k1的结点。检查结点是否仍在区间内后，如果结点仍然符合，则检查结点的右儿子。如果结点已经超出区间，则结点的右儿子中的所有元素都超出区间，不需要检查，返回上一个结点。故所有不符合条件的结点都不会被输出。\\


在去掉部分不在区间内的结点后，程序对于剩下的结点实际上是一个遍历的算法，故所有符合条件的元素都会被输出。\\


因此程序的算法正确。

\subsection{时间效率}
记树的节点数为N，符合输出条件的结点个数为K，程序声明不计时间。\\


当程序运行时，首先递归查找到了树中符合区间条件的最小结点。递归的次数与树的深度有关，由于使用AVL树，故递归的次数为logN次，这部分操作用时为$\Theta (logN) $。\\


之后程序在遍历所有符合输出条件的结点，对于每个结点元素的输出需要花费单位时间，这部分时间为$\Theta (K)$。\\


为了取到所有符合条件的结点，程序需要访问部分关键字已经大于k2，但是其左子树中包含符合输出条件的结点的结点。进入这部分结点后，程序先进入该结点的左儿子，再检查结点自身的元素，不访问其右子树。故这部分结点都处于根结点到符合输出条件的最大结点的路径上，总数不超过树的高度，这部分时间花费为$O(logN)$。\\


因此总的时间效率为$\Theta (K+logN)$


\section{数值结果分析}
分别记录程序固定N时程序运行时间随K值的变化,以及(T,logN)整数倍变化时运行时间的变化.
\begin{shaded}
\begin{verbatim}
ceviche@ceviche:~/chengxu/homework_3$ ./test | grep time
K = 1000  Average time = 50
K = 2000  Average time = 100
K = 3000  Average time = 144
K = 4000  Average time = 198
K = 5000  Average time = 241
K = 6000  Average time = 292
K = 7000  Average time = 348
K = 8000  Average time = 400
K = 9000  Average time = 452
N = 20  Average time = 1
N = 400  Average time = 2
N = 8000  Average time = 2
N = 160000  Average time = 5
N = 3200000  Average time = 6
N = 64000000  Average time = 7
\end{verbatim}
\end{shaded}
\begin{center}
\includegraphics[width = 10cm]{graphic/pic1.jpeg}
\\
\includegraphics[width = 10cm]{graphic/pic2.jpeg}
\end{center}
将数据绘制为折线图可看出，时间与T呈线性关系，与( T ,logN)大致呈线性关系。(电脑渣配置，只能跑成这样了)故运行时间为$\Theta (T+logN)$. 
\end{document}
